package com.datastructure.test.printfromtoptobottom;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class PrintFromTopToBottom {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {

    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> data = new ArrayList<>();
        if(root==null){
            return data;
        }
        levelOfIterator(root,0);
        for (ArrayList<Integer> list : res) {
            data.addAll(list);
        }
        return data;
    }

    private void levelOfIterator(TreeNode root, int i) {
        if(res.size()==i){
            res.add(new ArrayList<>());
        }
        ArrayList<Integer> list = res.get(i);
        list.add(root.val);
        if(root.left!=null){
            levelOfIterator(root.left,i+1);
        }
        if(root.right!=null){
            levelOfIterator(root.right,i+1);
        }
    }

    public ArrayList<Integer> PrintFromTopToBottom1(TreeNode root) {
        //queue用来保存当前遍历到了哪个节点，一次性把一个节点的左右子都入队
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //list用来保存输出的节点
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root==null){//注意：空树返回一个默认构造的空LinkedList，而不是一个空指针null
            return list;
        }
        TreeNode current = root;
        queue.offer(current);
        //只要队列中还有节点就说明还没遍历完，继续。
        //每次从队列出队，然后将这个节点左右子入队列（FIFO，故能完成广度/层级遍历），再将这个节点记录在list中即可。
        while(!queue.isEmpty()){
            current = queue.poll();
            list.add(current.val);
            if(current.left!=null){//有左子则入队
                queue.offer(current.left);
            }
            if(current.right!=null){
                queue.offer(current.right);
            }
        }
        return list;
    }

}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
